package com.leetcode.根据数据结构分类.数组;

import java.util.Arrays;

/**
 * @author: xiaomi
 * @date: 2021/4/4
 * @description: 781. 森林中的兔子
 * https://leetcode-cn.com/problems/rabbits-in-forest/
 */
public class B_781_森林中的兔子 {
    static B_781_森林中的兔子 action = new B_781_森林中的兔子();

    public static void main(String[] args) {
        test1();
        test2();
        test3();
    }

    static void test1() {
        //5
        int[] ans = new int[]{1, 0, 1, 0, 0};
        int res = action.numRabbits(ans);
        System.out.println("res = " + res);
    }

    static void test2() {
        //6
        int[] ans = new int[]{0, 0, 1, 1, 1};
        int res = action.numRabbits(ans);
        System.out.println("res = " + res);
    }

    static void test3() {
        //

        //System.out.println("res = " + res);
    }

    /**
     * 当相同的数量不足以支撑宽度时，就另外计算了
     * 找规律：
     * 1.当出现数字0时，代表没有其他的兔子同色，此时兔子数量 sum=1;
     * 2.当出现数字1时，代表有一只其他的兔子同色，最多可以维持[1,1](贪心，这样可以使兔子的数量最少),此时 sum=2;
     * 3.当出现数字2时，代表有2只其他的兔子同色，最多可以维持[2,2,2],此时 sum=3;
     * 同理...
     * 那么可以将 answers 进行排序，可以得到上述的数组形式，eg.[0,0,0,1,1,1,2,2,2,2,2]
     * 对于上述的例子可以分组为：
     * [0,0,0],[1,1],[1,(1)],[2,2,2],[2,2,(2)]
     * 一共13只。
     * (x)表示：没有列在 answers[] 中的兔子答案，但是在最少兔子情况下，必然会存在这样的兔子的回答。
     *
     * @param answers
     * @return
     */
    public int numRabbits(int[] answers) {
        Arrays.sort(answers);
        int len = answers.length;
        if (len == 0) {
            return 0;
        }
        //HashMap<Integer, Integer> map = new HashMap<>();
        int begin = 0;
        int sum = 0;
        for (int i = 1; i < len; i++) {
            if (answers[i] != answers[i - 1]) {
                //map.put(answers[i - 1], i - begin);
                int width = i - begin;
                int tempValue = answers[i - 1] + 1;
                if (width % tempValue == 0) {
                    // width / tempValue==对数 pairs
                    sum += width;
                } else {
                    sum += (width / tempValue + 1) * tempValue;
                }

                begin = i;
            }
        }
//        map.put(answers[len - 1], len - begin);
        int width = len - begin;
        int tempValue = answers[len - 1] + 1;
        if (width % tempValue == 0) {
            // width / tempValue==对数 pairs
            sum += width;
        } else {
            sum += (width / tempValue + 1) * tempValue;
        }

        return sum;
    }


}
